package main

// 单调递减栈维护，计算面积
func trap(height []int) int {
	stack := make([]int, 0)
	total := 0
	for i, num := range height {
		for len(stack) > 0 && height[stack[len(stack)-1]] < num {
			// 面积取决于三根柱子， 当前柱子num 和 栈顶元素， 和栈里的比栈顶高的柱子
			di := stack[len(stack)-1]
			stack = stack[:len(stack)-1]
			if len(stack) == 0 {
				break
			}
			// 取第三根柱子, 如果和底一样高，取不到水，去除掉
			// （这一块逻辑其实可以去掉，柱子一样高，计算的面积为0就完事儿了，不影响）
			// for len(stack) > 0 && height[stack[len(stack)-1]] == height[di] {
			//     stack = stack[:len(stack)-1]
			// }
			// if len(stack) == 0 {
			//     break
			// }
			left := stack[len(stack)-1]
			// 计算宽高, 面积
			width := i - left - 1
			high := min(num, height[left]) - height[di]
			total += width * high
		}
		stack = append(stack, i)
	}
	return total
}

func min(a, b int) int {
	if a < b {
		return a
	}
	return b
}
